int ans=0;
for (int a=1;a<=n;a++)
	ans += a;

for (int a=1;a<=n;a+=2) {
	ans += a;
	ans += a+1;
}

int s=(int)sqrt(n);
for (int a=1;a<=n;a++)
	belong[a]=(a-1)/s+1;
for (int a=1;a<=n;a++)
	right[belong[a]]=a;
for (int a=n;a>=1;a--)
	left[belong[a]]=a;
for (int a=1;a<=n;a++)
	sum[belong[a]]+=z[a];

int query(int l,int r) {
	int ans=0;
	if (belong[l]==belong[r]) {
		for (int a=l;a<=r;a++)
			ans+=z[a]+col[belong[a]];
	}
	else {
		for (int a=l;a<=right[belong[l]];a++)
			ans+=z[a]+col[belong[a]];
		for (int a=belong[l]+1;a<belong[r];a++)
			ans+=sum[a];
		for (int a=left[belong[r]];a<=r;a++)
			ans+=z[a]+col[belong[a]];
	}
	return ans;
}

void modify(int l,int r,int v) {
	if (belong[l]==belong[r]) {
		for (int a=l;a<=r;a++) {
			z[a]+=v;
			sum[belong[a]]+=v;
		}
	}
	else {
		for (int a=l;a<=right[belong[l]];a++) {
			z[a]+=v;
			sum[belong[a]]+=v;
		}
		for (int a=belong[l]+1;a<belong[r];a++) {
			col[a]+=v;
			sum[a]+=(right[a]-left[a]+1)*v;
		}
		for (int a=left[belong[r]];a<=r;a++) {
			z[a]+=v;
			sum[belong[a]]+=v;
		}
	}
}


struct query {
	int l,r,id;
	bool operator<(const query &a)const{
		if (belong[l]==belong[a.l]) return r<a.r;
		else return belong[l]<belong[a.l];
	}
}q[maxn];

sort(q+1,q+m+1);

int ans=0;
for (int a=q[1].l;a<=q[1].r;a++)
	ans+=z[a];
printf("%d\n",ans);
result[query[1].id]=ans;
for (int a=2;a<=m;a++) {
	if (q[a-1].l<=q[a].l) {
		for (int b=q[a-1].l;b<q[a].l;b++)
			ans-=z[b];
	}
	else {
		for (int b=q[a].l;b<q[a-1].l;b++)
			ans+=z[b];
	}
	if (q[a-1].r<q[a].r) {
		for (int b=q[a-1].r+1;b<=q[a].r;b++)
			ans+=z[b];
	}
	else {
		for (int b=q[a].r+1;b<=q[a-1].r;b++)
			ans-=z[b];
	}
}

http://www.lydsy.com/JudgeOnline/problem.php?id=2038

http://west14.openjudge.cn/true20170719/

void dfs(int now)
{
	cnt ++;
	left[now] = cnt;
	for p is now's son
		dfs(p);
	right[now] = cnt;
}

query(1,n,1,left[p],right[p]);

void dfs(int now)
{
	cnt ++;
	left[now] = cnt;
	for p is now's son
		dfs(p);
	cnt ++;
	right[now] = cnt;
}


void dfs(int now) {
	f[now][0]=father[now];
	for (int a=1;a<=19;a++)
		f[now][a]=f[f[now][a-1]][a-1];
	for p is now's son
		dfs(p);
}

int get_lca(int p1,int p2) {
	if (depth[p1]<depth[p2]) swap(p1,p2);
	int x=depth[p1]-depth[p2];
	int ans=0;
	for (int a=19;a>=0;a--)
		if (x&(1<<a)) {
			ans=max(ans,g[p1][a]);
			p1=f[p1][a];
		}
	for (int a=19;a>=0;a--)
		if (f[p1][a]!=f[p2][a]) {
			ans=max(ans,max(g[p1][a],g[p2][a]));
			p1=f[p1][a];
			p2=f[p2][a];
		}
	if (p1!=p2) {
		ans=max(ans,max(g[p1][0],g[p2][0]));
		p1=f[p1][0];
	}
	return ans;
}







